/*
 * @Author: xiguan
 * @Email: xiguan.teng@qq.com
 * @Version: 1.0
 * @Date: 2022-09-22 09:20:00
 * @LastEditTime: 2022-09-22 13:37:03
 */
#include <bits/stdc++.h>
#include <stdlib.h>

using namespace std;
typedef long long ll;

typedef struct trieNode{
    bool is_end;
    struct trieNode *Next_[26];
    trieNode(){
        is_end = false;
        fill( Next_, Next_ + 26, nullptr );
    }
}trieNode, *trieNodePtr;


typedef struct trie{
    trieNodePtr root;
    trie(){
        root = new trieNode;
    }

    void insert( const string &word ){
        auto p = root;
        for( auto x : word ){
            int index = x - 'a';
            if( !p->Next_[index] ){
                p->Next_[index] = new trieNode;    
            }
            p = p->Next_[index];
        }
        p->is_end = true;
    }

    bool search( const string &word ){
        auto p = root;
        for( auto x : word ){
            int index = x - 'a';
            if( !p->Next_[index] ){
                return false;
            }
            p = p->Next_[index];
        }
        return p->is_end;
    }

    bool startWith( const string &word ){
        auto p = root;
        for( auto x : word ){
            int index = x - 'a';
            if( !p->Next_[index] ){
                return false;
            }
            p = p->Next_[index];
        }
        return true;
    }

}trie;

int main( int argc, char *argv[] ){


    return 0;
}